<?php
/**
 * Created by PhpStorm.
 * User: admin
 * Date: 2019/2/16
 * Time: 11:26
 *
 * https://blog.csdn.net/qq_16399991/article/details/83866481
 */

class ListNode{
    var $val;
    var $next = null;
    function __construct($x){
        $this->val = $x;
    }
}

class LinkeList{

    public $header;

    /**
     * 创建不带头指针
     */
    public function constuctNoHeader()
    {
        $this->header = null;
    }

    /**
     * 创建带头链表
     */
    public function constuctWithHeader()
    {
        $this->header = new ListNode(null);
    }

    /**
     * 有头链表插入节点
     * @param $val
     */
    public function insert($val)
    {
        $node = new ListNode($val);
        $p = $this->header;
        while($p->next !=null){
            $p = $p->next;
        }
        $p->next = $node;
        return;
    }

    /**
     * 无头的链表插入节点
     * @param $val
     */
    public function inserNoHeader($val)
    {
        $node = new ListNode($val);
        if($this->header == null){
            $this->header = $node;
            return;
        }
        $p = $this->header;
        while($p->next !=null){
            $p = $p->next;
        }
        $p->next = $node;
        return;
    }

    /**
     * 有头链表删除元素
     * @param $val
     */
    public function delete($val)
    {
        $find = $this->header;
        //删除链表的后续部分
        while ($find->next && $find->next->val != $val){
            $find = $find->next;
        }

        //找到的位置存在两种情况 1.存在节点$val 这时find->next就是要删除的节点
        //2.不存在节点val，这时候find是最后一个节点
        if($find->next != null){
            $find->next = $find->next->next;
        }
        return;

    }

    /**
     * 删除无头链表的的一个节点
     * @param $val
     */
    public function deleteNoHeader($val)
    {
        if($this->header == null){
            return;
        }
        $find = $this->header;
        //删除的节点是链表的头
        if ($find->val == $val){
            $this->header = $find->next;
            return;
        }

        //删除链表的后续部分
        while ($find->next && $find->next->val != $val){
            $find = $find->next;
        }

        //找到的位置存在两种情况 1.存在节点$val 这时find->next就是要删除的节点
        //2.不存在节点val，这时候find是最后一个节点
        if($find->next != null){
            $find->next = $find->next->next;
        }
        return;
    }

    public function printList()
    {
        $p= $this->header;
        $res = [];
        while ($p->next){
            $res[] = $p->next->val;
            $p=$p->next;
        }

        echo implode('->', $res).PHP_EOL;
    }

    public function printListNoHeader()
    {
        $p= $this->header;
        $res = [];
        while ($p){
            $res[] = $p->val;
            $p=$p->next;
        }

        echo implode('->', $res).PHP_EOL;

    }
}

echo PHP_EOL."======no header=======".PHP_EOL;
//创建无头链表
$linkNoHeader = new LinkeList();
$linkNoHeader->constuctNoHeader();

$linkNoHeader->inserNoHeader(1);
$linkNoHeader->inserNoHeader(2);
$linkNoHeader->inserNoHeader(3);
$linkNoHeader->inserNoHeader(4);
$linkNoHeader->printListNoHeader();

//删除不存在
$linkNoHeader->deleteNoHeader(6);
$linkNoHeader->printListNoHeader();
//删除链表头
$linkNoHeader->deleteNoHeader(1);
$linkNoHeader->printListNoHeader();
//删除链表体
$linkNoHeader->deleteNoHeader(3);
$linkNoHeader->printListNoHeader();
//删除链表尾
$linkNoHeader->deleteNoHeader(4);
$linkNoHeader->printListNoHeader();

echo PHP_EOL."======have header=======".PHP_EOL;
//有头链表的
$linkHeader = new LinkeList();
$linkHeader->constuctWithHeader();

$linkHeader->insert(1);
$linkHeader->insert(2);
$linkHeader->insert(3);
$linkHeader->insert(4);
$linkHeader->printList();

$linkHeader->delete(6);
$linkHeader->printList();
//删除链头
$linkHeader->delete(1);
$linkHeader->printList();
//删除链体
$linkHeader->delete(3);
$linkHeader->printList();
//删除链表尾
$linkHeader->delete(4);
$linkHeader->printList();





